\section[Rings, Polynomials, and Finite Fields]{Rings, Polynomials, and Finite Fields \footnote{The content herein are a collection of important concepts and by no means provide a thorough coverage of the subject. Please read at your discretion and consult the provided references when necessary.}} \label{sec:Rings_Polys}


\subsection{Rings and Fields \cite{book:Fraleigh2003}}



Recall that a group is always defined along with a binary operation. It is possible to have more than a single operation for a set. This is the idea of rings. We formally define rings next.

\begin{Def} [Ring]
A set $R$ of elements under two binary operations, multiplication and addition, is a {\bf ring} provided that the following properties are satisfied:

\begin{enumerate}
	\item	$R$ forms an abelian group under addition
	\item	$R$ is associative under multiplication
	\item	(distributivity) if $a,b,c \in R$, then $a \times (b+c) = a \times b + a \times c$
\end{enumerate}
\end{Def}

The last property binds the two operation together. There are two important properties that simplify working with rings and fields and can be proved immediately.

\begin{Thrm}
Let $a \in R$ and $0$ be the additive identity in $R$. Then, $0.a=0$.
\end{Thrm}
\begin{proof}
Since $0$ is the additive identity, using the distributive property, we can write:
\[
a.0=a.(0+0)=a.0 + a.0 \Rightarrow a.0=0
\]
The last result is obtained by adding the additive inverse of $a.0$, namely $-(a.0)$, to either side.
\end{proof}

\begin{Thrm}
Let $a,b \in R$. Then $a(-b)=(-a)b=-ab$.
\end{Thrm}
\begin{proof}
From last theorem, we have:
\[
a.0=0 \Rightarrow a.(b+(-b))=0 \Rightarrow a.b + a.(-b) = 0
\]
The theorem result follows by adding the additive inverse of $a.b$ to both sides.
\end{proof}

There are several types of rings, next some definitions are provided in order to classify rings. Assume the additive identity is zero without loss of generality.

\begin{Def}
The multiplicative identity in a ring is called the {\bf unity}.
\end{Def}

\begin{Def}
If an element has a multiplicative inverse, it is called a {\bf unit}.
\end{Def}

\begin{Def}
A ring is {\bf commutative} if it is commutative under multiplication.
\end{Def}

We now know enough terminology to define a field.

\begin{Def} [Field]
A commutative ring with a unity where all the non-zero elements are units is a {\bf field}.
\end{Def}

\begin{Def}
let $a,b \in R$ be two non-zero elements such that $ab=0$. Then $a$ and $b$ are called {\bf zero divisors}. 
\end{Def}

\begin{eg}
In $\mathbb{Z}_{6}$, $2$ and $3$ are zero divisors since $2 \times 3 = 0$ mod $6$.
\end{eg}

\begin{Thrm}
In $\mathbb{Z}_{n}$, the zero divisors cannot be relatively prime with n.
\end{Thrm}
\begin{proof}
???
\end{proof}

\begin{Def} [Integral Domain]
A commutative ring that has no zero divisors is called an {\bf Integral Domain}.
\end{Def}

\begin{eg}
Let $p$ be a prime. Then $\mathbb{Z}_{p}$ is an Integral Domain since it has no zero divisors.
\end{eg}

\begin{Thrm} [Cancellation Law]
In an Integral Domain, the cancellation law  holds, i.e. $a.b=a.c \Rightarrow b=c$.
\end{Thrm}
\begin{proof}
We can write:
\[
a.b=a.c \Rightarrow a.(b+(-c))=0 \Rightarrow b+(-c)=0 \Rightarrow b=c
\]
The second last equality follows from the fact that there are no zero divisors, hence $a\neq0$.
\end{proof}

\begin{Thrm}
A finite Integral Domain is a field.
\end{Thrm}
\begin{proof} [by counting]
Let $D = \{0,1,a_{1}, \dots , a_{n}\}$ be an Integral Domain. Let's form a set by multiplying a fixed element $a_{i} \in D$ with all the elements of the group:
\[
\{ 0a_{i}=0,1a_{i}=a_{i},a_{1}a_{i}, \dots , a_{n}a_{i} \}
\]
By the cancellation law, these terms are all distinct. Therefore there is an element $a_{j} \in D$ such that $a_{j}a_{i}=1$. $a_{j}$ therefore is precisely the inverse and by this argument every element has an inverse, hence $D$ is a field.
\end{proof}

\begin{Thrm}
$\mathbb{Z}_{p}$ is a field for any prime number $p$.
\end{Thrm}

A very important parameter for a field is the characteristic of the field defined next.

\begin{Def}
An integer $n \in \mathbb{Z}$ is called the {\bf characteristic} number of a field $F$ if for every $a \in F$, $a.n=0$. 
\end{Def}

\begin{Thrm}
An integer $n \in \mathbb{Z}$ is the characteristic number of a field $F$ iff $1.n=0$.
\end{Thrm}
\begin{proof}
($\Rightarrow$) Proof in this case is trivial by the definition.\\
($\Leftarrow$) Let $a \in F$ any element of the field. Then we can write:

\[
a.n = \overbrace{(1+ \dots +1)}^\text{a times}.n = 1.n + \dots + 1.n = 0 + \dots + 0 = 0
\]
\end{proof}

In other words, the characteristic of a field is the additive order of $1$ (multiplicative identity).

\begin{Thrm}
The non-zero elements of a field $F$ form a group under multiplication - $F^{*}$.
\end{Thrm}

One of the most important theorems in the study of fields and polynomials is Fermat's little theorem. This theorem appears indefinitely in concepts such as polynomial factorization.

\begin{Thrm} [Fermat's Little Theorem]
For a prime number $p$ and $a \in \mathbb{Z}$, $a^{p-1}=1$ mod $p$.
\end{Thrm}
\begin{proof}
Let $a \in F_{p}$ by means of the modulo operation (more accurately, $a \in \mathbb{Z}/p\mathbb{Z}$ the factor group of $p\mathbb{Z}$) and let $G=\{1, \dots , p-1\}$ be the non-zero multiplicative group of $F_{p}$ with $p-1$ elements. We have $a^{|G|}=a^{p-1}=1$. 
\end{proof}

\begin{eg}
Find the remainder of $2^{342}$ divided by $23$?\\
By Fermat's Theorem we know $2^{22} = 1$ mod $23$. So,
\[
2^{342}=2^{22 \times 15+2}=(2^{22})^{15} \times 2^{2}=1 \times 2^{2} = 4 \text{ mod } 23
\]
\end{eg}

\begin{Thrm}
A finite $F^{*}$ is cyclic.
\end{Thrm}
\begin{proof}
$F^{*}$ is a finite group and abelian. By the Fundamental Theorem of Finitely Generated Abelian Groups, then $F^{*} \approx \mathbb{Z}_{q_{1}} \times \mathbb{Z}_{q_{2}} \times \dots \mathbb{Z}_{q_{n}}$ where $q_{i}$'s are powers of primes. Let $m=lcm(q_{1}, \dots, q_{n})$, then 
\[
m \leq q_{1} \dots q_{n}. 
\]
But also for all $\alpha \in \mathbb{Z}_{q_{1}} \times \mathbb{Z}_{q_{2}} \times \dots \mathbb{Z}_{q_{n}}$, by Fermat's Little Theorem we have $\alpha^{m}=1$ and more generally we have the equation $x^{m}-1=0$. The number of solutions to this equation (i.e. all $\alpha$'s, of which there are $q_{1} \dots q_{n}$) can be at most $m$. Therefore, 
\[
q_{1} \dots q_{n} \leq m
\]
So it must be that $q_{1} \dots q_{n} = m$ which means that the $q_{i}$'s are distinct and the direct product is isomorphic to $\mathbb{Z}_{m}$ which is cyclic.
\end{proof}

Much like the concept of normal groups and factor groups in group theory, there are sub-rings and sub-fields here called ideals. Ideals are an important concept in the study of finite fields and field extensions.

\begin{Def} [Ideal]
Let $R$ be a ring. An {\bf ideal} $I$ is a sub-ring of $R$ such that $aI=I,\forall a \in R$.
\end{Def}

\begin{Def} [Factor or Quotient Rings]
Let $R$ be a ring and $I$ an ideal. The {\bf Quotient Ring} $R/I$ is defined as:
\[
R/I =\{a+I | a \in R\}  
\]
and forms a ring under the following operations:
\[
(a+I)+(b+I)=(a+b)+I
\]
and,
\[
(a+I)(b+I)=(ab)+I
\]
\end{Def}

\begin{eg}
Find all the ideals of $\mathbb{Z}_{12}$?\\
The different ideals of $\mathbb{Z}_{12}$ are:
\[
\mathbb{Z}_{12}=\{0,1,\dots,11\}
\]
\[
2\mathbb{Z}_{12}=\{0,2,4,6,8,10\}
\]
\[
3\mathbb{Z}_{12}=\{0,3,6,9\}
\]
\[
4\mathbb{Z}_{12}=\{0,4,8\}
\]
\[
6\mathbb{Z}_{12}=\{0,6\}
\]
\end{eg}

\begin{Thrm}
If an ideal $I$ of a ring $R$ has a unit, then $I=R$.
\end{Thrm}
\begin{proof}
Let $a \in I$ be a unit. So for every $b \in R$, then $ba \in I$. Furthermore, since $a$ is a unit, $(ba)a^{-1}=baa^{-1}=b \in I$, hence $I=R$.  
\end{proof}

In the example above it can be seen that the only ideal containing $5$ (a unit in $\mathbb{Z}_{12}$) is $\mathbb{Z}_{12}$ itself. $\mathbb{Z}_{12}$ is called the {\bf improper} ideal. $\{0\}$ is the {\bf trivial} ideal of every ring. 

\begin{Def} [Maximal Ideal]
An ideal $I$ is a {\bf Maximal Ideal} if it is not contained in any other proper ideal. 
\end{Def}

\begin{Def} [Principal Ideal]
An ideal $I$ of a ring $R$ is a {\bf Principal Ideal} if $I=<a>=\{ra|r \in R\}$
\end{Def}

\begin{Thrm}
An ideal $I$ of a ring $R$ is Maximal iff $R/I$ is a field.
\end{Thrm}

Before starting the concept of polynomial rings, 3 more useful domains are introduced and will be made use of later on.

\begin{Def} [Unique Factorization Domain]
An Integral Domain $D$ is a {\bf Unique Factorization Domain} (UFD) if the following conditions are satisfied:
	\begin{enumerate}
		\item	Every non-zero non-unit element of $D$ can be factored into product of finite non-unit elements
		\item	If $p_{1} \dots p_{r}$ and $q_{1} \dots q_{s}$ are two factorizations of the same element in $D$, then $r=s$ and the terms can be renumbered so their are multiples of each other.
	\end{enumerate}
\end{Def}

\begin{Def} [Principal Ideal Domain]
An Integral Domain $D$ is a {\bf Principal Ideal Domain} (PID) if every ideal in $D$ is principal.
\end{Def}

\begin{Thrm} 
Every PID is is UFD.
\end{Thrm}

\begin{Thrm} \label{Thrm:PIDirrMaximal}
Let $p \in D$, where $D$ is a PID. Then, $<p>$ is maximal iff p is irreducible (i.e. $p \neq ab$).
\end{Thrm}
\begin{proof}
	\begin{enumerate}
		\item[($\Rightarrow$)] Suppose on the contrary $p=ab$. Then $<p> \subset <a>$ which contradicts $<p>$ being a maximal ideal.
		\item[($\Leftarrow$)] Let $<p> \subset <a>$, then $\exists b \in <a>$ such that $ab=p$. This contradicts the hypothesis that $p$ is irreducible.	
	\end{enumerate}
\end{proof}

\begin{Def} [Euclidean Domains]
An Integral Domain is a {\bf Euclidean Domain} if there is a mapping \emph{v} from non-zero elements to non-negative integers such that:
	\begin{enumerate}
		\item	For all $a,b \in D$ with $b \neq 0$, there exist $q$ and $r$ in $D$ such that $a=bq+r$ where $0 \leq v(r) < v(b)$.
		\item	For all $a,b \in D$, where neither $a$ nor $b$ is $0$, $v(a) \leq v(ab)$.
	\end{enumerate}
\end{Def}

\begin{eg}
The integers is a Euclidean Domain with the absolute value as its mapping. The result is the division algorithm $a=bq+r$. We will see that polynomials considering their degrees form a Euclidean Domain.
\end{eg}

\begin{Thrm}
Every Euclidean Domain is a UFD.
\end{Thrm}



\subsection{Polynomials \cite{book:Gallian2010}}



\begin{Def}
A {\bf polynomial} $f(x)$ of degree $n$ with coefficients $a_{i}$ in a ring $R$ is a sum in the form:
\[
\sum_{i=0}^{n} a_{i}x^{i}
\]
where $x$ is the indeterminate. 
\end{Def}

Certain axioms and properties of rings and fields follow in a similar manner for polynomials which are next discussed without proof.

\begin{Thrm} [Polynomial Rings]
The set of all the polynomials in indeterminate $x$ over a ring $R$ forms a ring under polynomial addition and multiplication and is denoted by $R[x]$. $R[x]$ has the following properties:
	\begin{enumerate}
		\item	If $R$ is commutative, so is $R[x]$.
		\item	If $R$ has a unity, so does $R[x]$.
		\item	If $R$ is an Integral Domain, so is $R[x]$.
		\item	If $R$ is a field, then $R[x]$ is an Integral Domain.
	\end{enumerate}
\end{Thrm}

\begin{Def} [Evaluation Homomorphism]
Let $E$ be a sub-field of $F$, $\alpha \in E$ and $f(x) \in F[x]$. The mapping $\phi: F[x] \rightarrow E$ is a homomorphism defined by:
\[
\phi_{\alpha}(f(x)): f(x) \rightarrow f(\alpha)
\]
$\phi_{\alpha}$ is called the {\bf Evaluation Homomorphism}, and $\phi_{\alpha}(x)=\alpha$ and $\phi_{\alpha}(a)=a$ where $a$ is a constant.
\end{Def}

A polynomial ring over an Integral Domain $R$ is a Euclidean Domain if the mapping $v$ in the definition of Euclidean Domains is taken to be degree of a polynomial. The following theorem then follows.

\begin{Thrm}
Every $f(x) \in F[x]$ can be written as:
\[
f(x) = p(x)q(x) + r(x),0 \leq deg(r(x)) < deg(p(x))
\]
for some $p(x) \in F[x]$.
\end{Thrm}

This theorem allows us to find greatest common divisors (gcd) for polynomials much like that of number field using Euclid's Algorithm.

\begin{Def} [zero of a polynomial]
An element $\alpha \in F$ is a zero of a polynomial $f(x) \in F[x]$ if $f(x)$ has $(x-\alpha)$ as a factor. In other words, if it can be written as:
\[
f(x) = (x-\alpha)h(x)
\]
where $h(x) \in F[x]$ is another polynomial of smaller degree. If $\alpha$ is a zero of $f(x)$ over $F$, then $f(\alpha)=0$.
\end{Def}

\begin{Thrm}
A polynomial of degree $m$ can have at most $m$ zeros.
\end{Thrm}

In what follows some general facts about {\bf irreducibility} of polynomials are stated. A polynomial is irreducible over some field if it has not zeros in that field. That is to say it cannot be factored over that field.

\begin{Thrm}
If $f(x)=x^{n}+ \dots + a_{1}x + a_{0} \in \mathbb{Z}[x]$ has a zero in $\mathbb{Q}$, then $f(x)$ has a zero in $\mathbb{Z}[x]$ and $m|a_{0}$.
\end{Thrm}

\begin{Thrm} [Eisenstein Criterion]
Let $p \in \mathbb{Z}$ be a prime. Suppose that $f(x)=a_{n}x^{n}+ \dots + a_{0}$ is in $\mathbb{Z}[x]$, and $a_{n} \neq 0$ (mod $p$), but $a_{i}=0$ (mod $p$) for all $i < n$, with $a_{0} \neq 0$ (mod $p^{2}$). Then $f(x)$ is irreducible over $\mathbb{Q}$.
\end{Thrm}

\begin{eg}
$25x^{5}-9x^{4}-3x^{2}-12$ is irreducible over $\mathbb{Q}$ by letting $p=3$ above.
\end{eg}

Recalling the discussion at the end of section \ref{sec:Rings_Polys}, next the concept of ideals and their relation with irreducibility is studied. Ideals can be defined over polynomials in a similar fashion to rings of regular elements. For instance, an idea $<x> \in F[x]$ is the principal ideal generated by $x$ which is in essence all multiples of $x$ in $F[x]$. It is apparent that $<x>$ is the collection of polynomials with zero constant terms.

\begin{Thrm}
If $F$ is a field, then $F[x]$ is a PID (i.e. every ideal in $F[x]$ is principal).
\end{Thrm}
\begin{proof}
Let $I$ be an ideal in $F[x]$ and let $p(x) \in I$ be the polynomial of smallest degree. Then for every $f(x) \in I$ we have:
\[
f(x) = p(x)q(x) + r(x), 0 \leq deg(r(x)) < deg(p(x)).
\]
But $r(x)$ with a degree less than $p(x)$ is in $I$ since $f(x) - p(x)q(x)$ is. Therefore $r(x)=0$ since $p(x)$ was picked as the polynomial with the smallest degree. 
\end{proof}

\begin{Thrm}
Let $F$ be a field. An ideal $<p(x)>$ in $F[x]$ is maximal iff $p(x)$ is irreducible.
\end{Thrm}
\begin{proof}
The proof is similar to that of Theorem \ref{Thrm:PIDirrMaximal}.
\end{proof}

Recall from section \ref{sec:Rings_Polys} that the quotient ring of a maximal ideal is a field. The same argument applies in this case. In fact, let $p(x) \in F[x]$ be an irreducible polynomial over $F$. It was shown above that $<p(x)>$ a maximal ideal. Therefore $F[x]/<p(x)>$ forms a field. This concept is used in the formation of cyclic codes in coding theory and will be examined more carefully in the remainder of this section.

\begin{Corollary}
Every ideal $I$ in $F[x]$, a PID, is generated by the smallest-degree polynomial in $I$.
\end{Corollary}

\begin{eg} [*Important] \label{eg:extention_fields}
Let us construct $F_{4}$ from $F=\mathbb{Z}_{2}$. Let $f(x)=x^{2}+x+1 \in \mathbb{Z}_{2}[x]$. Then $f(x)$ is irreducible (verify by substituting $0$ and $1$). By the above theorems $<x^{2}+x+1>$ is a maximal ideal generated by $f(x)$ and $\mathbb{Z}_{2}[x]/<x^{2}+x+1>$ is a field. Taking the representatives of the factor ring $\mathbb{Z}_{2}[x]/<x^{2}+x+1>$ we have:
\[
\mathbb{Z}_{2}[x]/<x^{2}+x+1>=\{a_{0}+a_{1}x|a_{0},a_{1} \in \mathbb{Z}_{2}\}=\{0,1,x,1+x\}
\]
To see that this is in fact a field, let's consider the Cayley Tables for addition and multiplication over this new field:\\

\begin{center}
\begin{tabular}{c | c c c c }
$+$ & $0$ & $1$ & $x$ & $1+x$ \\
\hline
$0$ & $0$ & $1$ & $x$ & $1+x$ \\
$1$ & $1$ & $0$ & $1+x$ & $x$ \\
$x$ & $x$ & $1+x$ & $0$ & $1$ \\
$1+x$ & $1+x$ & $x$ & $1$ & $0$
\end{tabular}\\
\end{center}

Clearly each element has an inverse and the group is abelian under addition. As for multiplicatoin:\\

\begin{center}
\begin{tabular}{c | c c c c }
$\times$ & $0$ & $1$ & $x$ & $1+x$ \\
\hline
$0$ & $0$ & $0$ & $0$ & $0$ \\
$1$ & $0$ & $1$ & $x$ & $1+x$ \\
$x$ & $0$ & $x$ & $1+x$ & $1$ \\
$1+x$ & $0$ & $1+x$ & $1$ & $x$
\end{tabular}\\
\end{center}

keeping in mind that in this field $x^{2}+x+1=0$. It can be seen that the non-zero elements (i.e. $F_{4}^{*}$) form an abelian group under multiplication.
\end{eg}

The idea behind this example can be extended to generate all powers of prime easily, such as $F_{8}$ and $F_{16}$ from $\mathbb{Z}_{2}$ or $F_{9}$ from $\mathbb{Z}_{3}$.

\begin{Def} [Extension Fields]
Let $E$ and $F$ be fields such that $F < E$. Then $E$ is called an {\bf extension field} of $F$.
\end{Def}

\begin{Thrm} [Kroneker's Theorem] \label{Thrm:Kroneker}
Let $f(x) \in F[x]$ be a non-constant polynomial. There exists an extention field $E$ such that $f(\alpha)=0$ for some $\alpha \in E$.
\end{Thrm}

Theorem \ref{Thrm:Kroneker} is also known as the {\bf Fundamental Theorem of Field Theory}. In Example \ref{eg:extention_fields} it was observed how starting from $\mathbb{Z}_{2}$ a field $\mathbb{Z}_{2}[x]/<x^{2}+x+1>$  of order $4$ was generated. The latter is an extension field of $\mathbb{Z}_{2}$ and although $x^{2}+x+1$ does not have a zero in $\mathbb{Z}_{2}$, it certainly does in the new field. There are particular extension fields that are worthwhile looking into which is the goal of what follows.

\begin{Def} [Splitting Field]
Let $E$ be an extension field for $F$. If $f(x) \in F[x]$ splits into linear factors in $E[x]$ but in no proper subfield of $E[x]$, then $E$ is an {\bf splitting field} for $f(x)$ over $F$. 
\end{Def}

\begin{Thrm}
Let $F$ be a field and let $f(x)$ be a non-constant element of $F[x]$, then there exists a unique splitting field $E$ for $f(x)$ over $F$.
\end{Thrm}
\begin{proof}
The proof is trivial if $f(x)$ splits in $F[x]$. If not, then using Theorem \ref{Thrm:Kroneker} a splitting extension can be found.
\end{proof}

\begin{eg} \label{eg:splitting}
In Example \ref{eg:extention_fields}, what is the linear factorization of $f(x)=x^{2}+x+1 \in \mathbb{Z}_{2}[x]$ over $F_{4}$?\\

The splitting field obtained is $F_{4}=\mathbb{Z}_{2}[x]/<x^{2}+x+1>=\{0,1,x,1+x\}$ which clearly is an extension of $\mathbb{Z}_{2}$. Let $x=\beta$ so not to confuse $x$ with the indeterminate $x$ in the polynomial. Thus we have $F_{4}=\{0,1,\beta,1+\beta\}$. From $f(x)$ it is obvious that $f(\beta)=\beta^{2}+\beta+1=0$ (by substituting in $f(x)$). So $\beta$ is a zero. To find the other zero, let us use the long division since a field is also a $PID$. Long division results in:
\begin{eqnarray}
x^{2}+x+1&=&(x-\beta)(x+\beta+1)+(1+\beta(1+\beta)) \nonumber \\
&=&(x-\beta)(x+\beta+1)+(1+\beta+\beta^{2}) \nonumber \\
&=&(x-\beta)(x+\beta+1)+0 \nonumber \\
&=&(x-\beta)(x+\beta+1) \nonumber 
\end{eqnarray}
Therefore, $\beta$ and $1+\beta$ are the zeros and the factorization is the last result above.
\end{eg}

Another type of extension is the field of quotients of $F[x]$ for a field $F$ defined below.

\begin{Def} [the Field of Quotients] \label{Def:quotient_fields}
Let $F$ be a field. Then the {\bf Field of Quotients} of $F[x]$ denoted by $F(x)$ is defined as:
\[
F(x)=\{ \frac{f(x)}{g(x)} | f(x),g(x) \in F[x],g(x) \neq 0\}
\]
\end{Def}

This type of extension is also called {\bf simple extension}. 

\begin{eg} \label{eg:Q_sqrt2}
Let us find $\mathbb{Q}(\sqrt{2})$?\\

By definition \ref{Def:quotient_fields}, we have:
\[
\mathbb{Q}(\sqrt{2})=\{ \frac{f(\sqrt{2})}{g(\sqrt{2})} | f(x),g(x) \in \mathbb{Q},g(x) \neq 0\}
\]
By algebraic manipulation, the numerator and denominator of $f(\sqrt{2})/g(\sqrt{2})$ can be rewritten in the form:
\[
\frac{f(\sqrt{2})}{g(\sqrt{2})} = \frac{a\sqrt{2}+b}{c\sqrt{2}+d}
\]
where $a,b,c,d \in \mathbb{Q}$. Multiplying by the conjugate of the denominator, we finally obtain:
\[
\mathbb{Q}(\sqrt{2})=\{ a+b\sqrt{2} | a,b \in \mathbb{Q} \}
\]
\end{eg}

The result above turns out to be the same if instead a irreducible polynomial in $\mathbb{Q}$ with $\sqrt{2}$ as a zero was used. But first $2$ other important extensions are introduced.

\begin{Def} [Algebraic Extension]
An element $\alpha$ in $E$, an extension of $F$, is {\bf algebric} over $F$ if there exists $f(x) \in F[x]$ such that $f(\alpha)=0$. A field $E$ is called an {\bf algebraic extension} of a field $F$ if every element in $E$ is algebraic over $F$. 
\end{Def}

\begin{eg}
$\beta$ in Example \label{eg:splitting} is algebraic over $\mathbb{Z}_{2}$ since letting $f(x)=x^{2}+x+1 \in \mathbb{Z}_{2}[x]$ then $f(\beta)=0$. Furthermore, $\mathbb{Z}_{2}[x]/<f(x)$ is algebraic extension of $\mathbb{Z}_{2}$.
\end{eg}

\begin{Thrm}
If $\alpha \in E$ is algebraic over a field $F$, then there is a unique monic irreducible polynomial $p(x)$ in $F[x]$ such that $p(\alpha)=0$. If $f(x) \in F[x]$ and $f(\alpha)=0$, then $p(x)$ divides $f(x)$. 
\end{Thrm}

\begin{Def} [Transcendental Extension]
An element that is not algebraic is called {\bf transcendental}. A field $E$ is called a {\bf transcendental extension} of a field $F$ if every element in $E$ is transcendental over $F$.
\end{Def}

\begin{eg}
Numbers $e$ and $\pi$ are transcendental over $\mathbb{Q}$!
\end{eg}

\begin{Def} [Algebraic Closure and Algebraically Closed]
Let $E$ be an extension of $F$. The set of elements of $E$ that are algebraic over $F$ forms a sub-field of $E$ called the {\bf algebraic closure} of $F$ in $E$.A field that has no proper algebraic extension is {\bf algebraically closed}.
\end{Def}

A field $E$ is algebraically closed if all the if all polynomials in $E[x]$ split over $E$. It is been proved that the set of complex numbers $\mathbb{C}$ is algebraically closed. The next theorem relates the different extensions covered above.

\begin{Thrm} [Characterization of Extensions] \label{Thrm:Char_of_Extensions}
Let $E$ be an extension field of the field $F$ and let $\alpha \in E$. If $\alpha$ is transcendental over $F$, then $F(\alpha) \approx F(x)$. If $\alpha$ is algebraic over $F$, then $F(\alpha) \approx F[x]/<p(x)>$ where $p(x)$ is an irreducible polynomial over $F$ such that $p(\alpha)=0$. 
\end{Thrm}

The characteristic of a field is an important property of the field. Below a special class of fields is defined.

\begin{Def} [Perfect Field]
A field $F$ with characteristic $p$ in which $p = 0$ or  $F^{p}=\{a^{p}|a \in F\}=F$ is called a {\bf perfect field}. 
\end{Def}

\begin{Thrm}
Every finite field is also perfect.
\end{Thrm}

\begin{Thrm}
Let $F$ be a perfect field and $f(x) \in F[x]$ be an irreducible polynomial. Then $f(x)$ has no multiple zeros (i.e. zero of multiplicity greater than one).
\end{Thrm}

\begin{Thrm} \label{Thrm:split_factors}
Let $f(x)$ be an irreducible polynomial over a field $F$ and $E$ a splitting field of $f(x)$. Then $f(x)$ has the form:
\[
a(x-a_{1})^{n} \dots (x-a_{m})^{n}
\]
where $a_{1}, \dots , a_{m}$ are distinct elements of $E$ and $a \in F$.
\end{Thrm}

The above theorem comes handy in the study of polynomial factorization over arbitrary fields. Before starting to talk about the structure of Finite Fields in particular, another important concept that brings the idea of vector spaces into field theory is worth looking into.  

\begin{Thrm}
Let $E$ be an algebraic extension of $F$ with respect to an irreducible polynomial $p(x) \in F[x]$ such that $p(\alpha)=0$ for some $\alpha \in E$. If $deg(p(x))=n$, then every element $\beta \in E$ can be written in the form:
\[
\beta = c_{n-1}\alpha^{n-1}+c_{n-2}\alpha^{n-1}+ \dots + c_{1}\alpha + c_{0}
\]
where $c_{n-1},c_{n-2}, \dots ,c_{1},c_{0} \in F$.
\end{Thrm}
\begin{proof}
By Theorem \ref{Thrm:Char_of_Extensions} we have $E=F(\alpha)$ (the smallest extension of $F$ containing $\alpha$) and also $F(\alpha)$ is isomorphic to $F[x]/<p(x)>$. Now every polynomial $f(x)$ in the latter quotient field can be written as:
\[
f(x)=c_{n-1}x^{n-1}+c_{n-2}x^{n-1}+ \dots + c_{1}x + c_{0}
\] 
By properties of isomorphism therefore,
\[
\beta = c_{n-1}\alpha^{n-1}+c_{n-2}\alpha^{n-1}+ \dots + c_{1}\alpha + c_{0}
\]
for some $\beta \in E$.
\end{proof}

\begin{Corollary} [Vector Spaces]
Let $E$ be an algebraic extension of $F$ with respect to an irreducible polynomial $p(x) \in F[x]$ such that $p(\alpha)=0$ for some $\alpha \in E$ and $deg(p(x))=n$. Then $E$ is a vector space of dimension $n$ with vector addition defined over elements of $E$ and scalar multiplication over elements of $F$.
\end{Corollary}

\begin{eg}
In Example \ref{eg:Q_sqrt2}, it was shown that the extension $\mathbb{Q}(\sqrt{2})$ of $\mathbb{Q}$ is:
\[
\mathbb{Q}(\sqrt{2})=\{ a+b\sqrt{2} | a,b \in \mathbb{Q} \}
\]
Therefore $\mathbb{Q}(\sqrt{2})$ is a vector space over $\mathbb{Q}$ of dimension $2$ (let $p(x)=x^{2}-2$) with a basis $\{1,\sqrt{2}\}$.
\end{eg}

\begin{Corollary}
Let $E$ be a finite extension of degree $n$ over a finite field $F$. If $F$ has $q$ elements, then $E$ has $q^{n}$ elements \cite{book:Fraleigh2003}.
\end{Corollary}

%finite fields
\subsection{Finite Fields \cite{book:Gallian2010}}

In this section, the structure of finite fields is to be studied. As it turns out, finite fields are very "simple" in structure and easy to generalize. To start, a general theorem that follows from the concept of vector spaces in field theory is stated.

\begin{Thrm}
If $E$ is a finite field of characteristic $p$, then $E$ contains exactly $p^{n}$ elements for some positive integer $n$ \cite{book:Fraleigh2003}.
\end{Thrm}
\begin{proof}
A finite extension $E$ of characteristic $p$ is isomorphic to $\mathbb{Z}_{p}$. The corollary then immediately follows. 
\end{proof}

\begin{Thrm}
Let $f(x)=x^{p^{n}}-x \in \mathbb{Z}_{p}[x]$ and $E$ the splitting field of $\mathbb{Z}_{p}$ for $f(x)$. Then $E$ has precisely $p^{n}$ (a prime-power) elements which are the zeros of $f(x)$.
\end{Thrm}
\begin{proof}
$f(x)$ has at most $p^{n}$ zeros and since $gcd(f(x),f^{'}(x))=1$ it does not have any multiple zeros. Therefore by Theorem \ref{Thrm:split_factors} $f(x)= a(x-a_{1}) \dots (x-a_{p^{n}})$ over $E$.
\end{proof}

\begin{Thrm}
For each prime $p$ and each positive integer $n$, there is, up to isomorphism, a unique finite field of order $p^{n}$.
\end{Thrm}
\begin{proof}
By the previous Theorem, the finite field is constructed from the zeros of $x^{p^{n}}-x$.
\end{proof}

This theorem indicates that for every prime power there is a unique finite field and is called the {\bf Galois field} of order $p^{n}$ and denoted by $GF(p^{n})$.

\begin{Thrm}
As a group under addition, $GF(p^{n})$ is isomorphic to the direct product:
\[
\overbrace{ \mathbb{Z}_{p} \oplus \mathbb{Z}_{p} \oplus \dots \oplus \mathbb{Z}_{p} }^\text{n factors}
\]
As a group under multiplication, the set of nonzero elements of $GF(p^{n})$ is isomorphic to $\mathbb{Z}_{p^{n}-1}$ and is cyclic.
\end{Thrm}

\begin{Thrm}
For each divisor $m$ of $n$, $GF(p^{n})$ has a unique subfield of order $p^{m}$. Moreover, these are the only sibfields of $GF(p^{n})$.
\end{Thrm}
  
\begin{Thrm}
If $F$ is a field of prime characteristic $p$, then $(\alpha + \beta)^{p^{n}} = \alpha^{p^{n}} + \beta^{p^{n}}$ for all $\alpha,\beta \in F$ and positive integers $n$.
\end{Thrm}
\begin{proof}
The proof follows a mathematical induction. Here the case of $n=1$ is shown:
\begin{eqnarray}
(\alpha + \beta)^{p} &=& \alpha^{p} + \binom{p}{1}\alpha^{p-1}\beta + \binom{p}{2}\alpha^{p-2}\beta^{2} \nonumber \\
&+& \dots + \binom{p}{p-1}\alpha\beta^{p-1}+ \beta^{p} = \alpha^{p^{n}} + \beta^{p^{n}}  \nonumber
\end{eqnarray}
where the last result follows since each term other than those remaining has a factor of $p=1.p=0$.
\end{proof}

At this point, one can picture the structure of any finite field in terms of order, additive and multiplicative structure, and sub-fields. As a last step, another example that brings all these ideas together is provided. 

\begin{eg}
Take irreducible $f(x)=x^{3}+x^{2}+1$ over $\mathbb{Z}_{2}$. Then for $E=\mathbb{Z}_{2}[x]/<f(x)>$ there are $2^3=8$ elements ($p=2,n=3$). Without attempting to find the individual elements, based on the knowledge of finite fields, we can write:
\[
E = \{0,1,\alpha,\alpha^{2},\alpha^{3},\alpha^{4},\alpha^{5},\alpha^{6}\}
\]
where $\alpha$ is the generator of the multiplicative of $E$ and the set is written based on the fact that $E^{*}\approx \mathbb{Z}_{p^{n}-1} =  \mathbb{Z}_{7}$. But it is also known that under addition $E$ is isomorphic to a direct product and thereby to $\mathbb{Z}_{p^{n}}$. Keeping in mind the original relation $f(\alpha)=\alpha^{3}+\alpha^{2}+1=0$, we can also write:
\[
E = \{0,1,\alpha,\alpha+1,\alpha^{2},\alpha^{2}+\alpha+1,\alpha^{2}+1,\alpha^{2}+\alpha\}
\]
using the computation:
\[
\alpha^{3}= \alpha^{2}+1 \Rightarrow \alpha^{4}= \alpha^{3}+\alpha=(\alpha^{2}+1)+\alpha \Rightarrow \alpha^{4}=\alpha^{2}+\alpha+1
\]
and similarly, 
\begin{eqnarray}
\alpha^{5}=\alpha+1 \nonumber \\
\alpha^{6}=\alpha^{2}+\alpha \nonumber \\
\alpha^{7}=1 \nonumber
\end{eqnarray}
The two interpretations of $E$ are the same and it comes down to ease of computation. The first form is easy for multiplicative computations while the second form makes addition convenient. 
\end{eg} 




